﻿// CREDITS to Tawani Anyangwe: http://tawani.blogspot.de/2009/02/topological-sorting-and-cyclic.html

namespace Smartstore.Collections
{
    public interface ITopologicSortable<TKey>
    {
        TKey Key { get; }
        TKey[] DependsOn { get; }
    }

    public static class TopologicalSortExtensions
    {
        public static ITopologicSortable<T>[] SortTopological<T>(this ITopologicSortable<T>[] items)
        {
            return SortTopological(items, null);
        }

        public static ITopologicSortable<T>[] SortTopological<T>(this ITopologicSortable<T>[] items, IEqualityComparer<T> comparer)
        {
            Guard.NotNull(items, nameof(items));

            var sortedIndexes = SortIndexesTopological(items, comparer);
            var sortedList = new List<ITopologicSortable<T>>(sortedIndexes.Length);

            for (var i = 0; i < sortedIndexes.Length; i++)
            {
                //sortedList[i] = items[sortedIndexes[i]];
                sortedList.Add(items[sortedIndexes[i]]);
            }

            return sortedList.ToArray();
        }

        private static int[] SortIndexesTopological<T>(ITopologicSortable<T>[] items) 
            => SortIndexesTopological(items, null);

        private static int[] SortIndexesTopological<T>(ITopologicSortable<T>[] items, IEqualityComparer<T> comparer)
        {
            Guard.NotNull(items);

            if (items.Length == 0)
            {
                return [];
            }

            if (comparer == null)
            {
                comparer = EqualityComparer<T>.Default;
            }

            var sorter = new TopologicalSorter(items.Length);
            var indexes = new Dictionary<T, int>(comparer);

            // add vertices
            for (int i = 0; i < items.Length; i++)
            {
                indexes[items[i].Key] = sorter.AddVertex(i);
            }

            // add edges
            for (int i = 0; i < items.Length; i++)
            {
                if (items[i].DependsOn != null)
                {
                    for (int j = 0; j < items[i].DependsOn.Length; j++)
                    {
                        if (indexes.ContainsKey(items[i].DependsOn[j]))
                        {
                            sorter.AddEdge(i, indexes[items[i].DependsOn[j]]);
                        }
                    }
                }
            }

            int[] result = sorter.Sort().Reverse().ToArray();
            return result;
        }
    }

    public class CyclicDependencyException : Exception
    {
        public CyclicDependencyException()
            : base("Cyclic dependency detected")
        {
        }

        public CyclicDependencyException(string message)
            : base(message)
        {
        }
    }

    internal class TopologicalSorter
    {
        #region Private Members

        private readonly int[] _vertices; // list of vertices
        private readonly int[,] _matrix; // adjacency matrix
        private int _numVerts; // current number of vertices
        private readonly int[] _sortedArray;

        #endregion

        #region Ctor

        public TopologicalSorter(int size)
        {
            _vertices = new int[size];
            _matrix = new int[size, size];
            _numVerts = 0;
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    _matrix[i, j] = 0;
                }
            }
            _sortedArray = new int[size]; // sorted vert labels
        }

        #endregion

        #region Public Methods

        public int AddVertex(int vertex)
        {
            _vertices[_numVerts++] = vertex;
            return _numVerts - 1;
        }

        public void AddEdge(int start, int end)
        {
            _matrix[start, end] = 1;
        }

        public int[] Sort() // topological sort
        {
            while (_numVerts > 0) // while vertices remain,
            {
                // get a vertex with no successors, or -1
                int currentVertex = NoSuccessors();
                if (currentVertex == -1)
                {
                    // must be a cycle                
                    throw new CyclicDependencyException();
                }

                // insert vertex label in sorted array (start at end)
                _sortedArray[_numVerts - 1] = _vertices[currentVertex];

                DeleteVertex(currentVertex); // delete vertex
            }

            // vertices all gone; return sortedArray
            return _sortedArray;
        }

        #endregion

        #region Private Helper Methods

        // returns vert with no successors (or -1 if no such verts)
        private int NoSuccessors()
        {
            for (int row = 0; row < _numVerts; row++)
            {
                bool isEdge = false; // edge from row to column in adjMat
                for (int col = 0; col < _numVerts; col++)
                {
                    if (_matrix[row, col] > 0) // if edge to another,
                    {
                        isEdge = true;
                        break; // this vertex has a successor try another
                    }
                }
                if (!isEdge) // if no edges, has no successors
                    return row;
            }
            return -1; // no
        }

        private void DeleteVertex(int delVert)
        {
            // if not last vertex, delete from vertexList
            if (delVert != _numVerts - 1)
            {
                for (int j = delVert; j < _numVerts - 1; j++)
                    _vertices[j] = _vertices[j + 1];

                for (int row = delVert; row < _numVerts - 1; row++)
                    MoveRowUp(row, _numVerts);

                for (int col = delVert; col < _numVerts - 1; col++)
                    MoveColLeft(col, _numVerts - 1);
            }
            _numVerts--; // one less vertex
        }

        private void MoveRowUp(int row, int length)
        {
            for (int col = 0; col < length; col++)
                _matrix[row, col] = _matrix[row + 1, col];
        }

        private void MoveColLeft(int col, int length)
        {
            for (int row = 0; row < length; row++)
                _matrix[row, col] = _matrix[row, col + 1];
        }

        #endregion
    }
}
